/**
 * Author: Yuan Li
 * Title: lab5 for 15121 summer
 */

import java.util.Collection;
import java.util.Comparator;
import java.util.Iterator;
import java.util.Queue;
import java.util.AbstractQueue;
import java.util.SortedSet;
import java.util.NoSuchElementException;

/**
 * An unbounded priority {@linkplain Queue queue}. This queue orders elements
 * according to an order specified at construction time, which is specified
 * either according to their <i>natural order</i> (see {@link Comparable}), or
 * according to a {@link java.util.Comparator}, depending on which constructor
 * is used. A priority queue does not permit <tt>null</tt> elements. A
 * priority queue relying on natural ordering also does not permit insertion of
 * non-comparable objects (doing so may result in <tt>ClassCastException</tt>).
 * <p>
 * The <em>head</em> of this queue is the <em>least</em> element with
 * respect to the specified ordering. If multiple elements are tied for least
 * value, the head is one of those elements -- ties are broken arbitrarily. The
 * queue retrieval operations <tt>poll</tt>, <tt>remove</tt>,
 * <tt>peek</tt>, and <tt>element</tt> access the element at the head of
 * the queue.
 * <p>
 * A priority queue is unbounded, but has an internal <i>capacity</i> governing
 * the size of an array used to store the elements on the queue. It is always at
 * least as large as the queue size. As elements are added to a priority queue,
 * its capacity grows automatically. The details of the growth policy are not
 * specified.
 * <p>
 * This class and its iterator implement all of the <em>optional</em> methods
 * of the {@link Collection} and {@link Iterator} interfaces. The Iterator
 * provided in method {@link #iterator()} is <em>not</em> guaranteed to
 * traverse the elements of the PriorityQueue in any particular order. If you
 * need ordered traversal, consider using <tt>Arrays.sort(pq.toArray())</tt>.
 * <p>
 * <strong>Note that this implementation is not synchronized.</strong> Multiple
 * threads should not access a <tt>PriorityQueue</tt> instance concurrently if
 * any of the threads modifies the list structurally. Instead, use the
 * thread-safe {@link java.util.concurrent.PriorityBlockingQueue} class.
 * <p>
 * Implementation note: this implementation provides O(log(n)) time for the
 * insertion methods (<tt>offer</tt>, <tt>poll</tt>, <tt>remove()</tt>
 * and <tt>add</tt>) methods; linear time for the <tt>remove(Object)</tt>
 * and <tt>contains(Object)</tt> methods; and constant time for the retrieval
 * methods (<tt>peek</tt>, <tt>element</tt>, and <tt>size</tt>).
 */
@SuppressWarnings("unchecked")
public class PriorityQueue<T> extends AbstractQueue<T> {
	
	/** DO NOT CHANGE */
	private static final int DEFAULT_INITIAL_CAPACITY = 16;
	
	private T[] array;
	
	private Comparator<? super T> comparator;
	
	private int size;
	
	private int slot;
	
	/**
	 * Creates a <tt>PriorityQueue</tt> with the default initial capacity (16)
	 * that orders its elements according to their natural ordering (using
	 * <tt>Comparable</tt>).
	 */
	public PriorityQueue ()
	{
		this.size = DEFAULT_INITIAL_CAPACITY;
		// not sure whether this will work
		this.array = (T[]) new Object[this.size];
		this.slot = 1;
		this.comparator = null;
	}

	/**
	 * Creates a <tt>PriorityQueue</tt> with the specified initial capacity
	 * that orders its elements according to their natural ordering (using
	 * <tt>Comparable</tt>).
	 * 
	 * @param initialCapacity
	 *            the initial capacity for this priority queue.
	 * @throws IllegalArgumentException
	 *             if <tt>initialCapacity</tt> is less than 1
	 */
	public PriorityQueue (int initialCapacity)
	{
		// check the input param
		if (initialCapacity < 1){
			throw new IllegalArgumentException("initialCapacity is below 1");
		}
		
		this.size = initialCapacity;
		this.array = (T[]) new Object[this.size];
		this.slot = 1;
		this.comparator = null;
	}

	/**
	 * Creates a <tt>PriorityQueue</tt> with the specified initial capacity
	 * that orders its elements according to the specified comparator.
	 * 
	 * @param initialCapacity
	 *            the initial capacity for this priority queue.
	 * @param comparator
	 *            the comparator used to order this priority queue. If
	 *            <tt>null</tt> then the order depends on the elements'
	 *            natural ordering.
	 * @throws IllegalArgumentException
	 *             if <tt>initialCapacity</tt> is less than 1
	 */
	public PriorityQueue (int initialCapacity, Comparator<? super T> comparator)
	{
		// check the input param
		if (initialCapacity < 1){
			throw new IllegalArgumentException("initialCapacity is below 1");
		}
		
		this.size = initialCapacity;
		this.array = (T[]) new Object[this.size];
		this.slot = 1;
		this.comparator = comparator;
	}
	
	/**
	 * Creates a <tt>PriorityQueue</tt> that orders its elements according to the specified comparator.
	 * 
	 * @param comparator
	 *            the comparator used to order this priority queue. If
	 *            <tt>null</tt> then the order depends on the elements'
	 *            natural ordering.
	 */
	public PriorityQueue (Comparator<? super T> comparator)
	{
		this.size = DEFAULT_INITIAL_CAPACITY;
		// not sure whether this will work
		this.array = (T[]) new Object[this.size];
		this.slot = 1;
		this.comparator = comparator;
	}


	/**
	 * Returns the comparator used to order this collection, or <tt>null</tt>
	 * if this collection is sorted according to its elements natural ordering
	 * (using <tt>Comparable</tt>).
	 * 
	 * @return the comparator used to order this collection, or <tt>null</tt>
	 *         if this collection is sorted according to its elements natural
	 *         ordering.
	 */
	public Comparator<? super T> comparator ()
	{
		return this.comparator;
	}


	@Override
    public int size ()
	{
		return this.slot-1;
	}
	
	
	@Override
	public boolean isEmpty()
	{
		if (this.slot == 1){
			return true;
		}
		else{
			return false;
		}
	}
	
	/**
	 * percolate -- will select to use nature ordering or comparator to implement the percolate
	 * @param index -- index of current node
	 * @return -- return true if successfully percolate
	 */
	private boolean percolate(int index){
		//check the input parameters
		if (index <= 0 ){
			System.out.println("index belows 0");
			return false;
		}
		
		// for the root, do nothing
		if (index == 1){
			return true;
		}
		
		// compute parent by integer dividing 2
		int parent = index / 2;
		if (parent == 0){
			return true;
		}
		
		// if we can use nature ordering
		if (this.comparator == null){
			int result = ((Comparable) this.array[parent]).compareTo(this.array[index]);
			// for the equal case, we adopt FIFO policy, thus do not swap
			// if parent < current
			if (result > 0){
				// swap parent and current
				T tmp;
				tmp = this.array[parent];
				this.array[parent] = this.array[index];
				this.array[index] = tmp;
				
				// recursively percolate
				if (percolate(parent)){
					return true;
				}
				else{
					return false;
				}
			}
			// if parent >= current
			else{
				return true;
			}
			
			
			
		}
		// we have to use the comparator
		else{
			int result = this.comparator.compare(this.array[parent], this.array[index]);
			// if parent < current
			if (result > 0){
				//swap parent and current
				T tmp;
				tmp = this.array[parent];
				this.array[parent] = this.array[index];
				this.array[index] = tmp;
				// recursively percolate
				if (percolate(parent)){
					return true;
				}
				else{
					return false;
				}
			}
			// if parent >= current
			else{
				return true;
			}
		}
	}
	
	/**
	 * resize -- will make the size of heap double
	 */
	private void resize(){
		// create a twice size array
		this.size = this.size * 2;
		T[] tmp = (T[]) new Object[this.size];
		
		// deep copy every element from the older array to the new
		for (int i=1; i < array.length; i++){
			tmp[i] = this.array[i];
		}
		
		// use new array to replace the old one
		this.array = tmp;
	}
	
	/**
	 * percolateDown -- percolate down left to maintain the property of the binary heap
	 * @param curr -- index of the current node
	 * @return -- return true if successfull, vice versa
	 * verse
	 */
	private boolean percolateDown(int curr){
		// check the input parameter
		if (curr <= 0){
			System.out.println("the index of current node is below 1");
			return false;
		}
		// out of ranger of heap
		if (curr >= this.slot){
			System.out.println("current node out of heap range at percolateDown");
			return false;
		}
		
		// compute left and right child of current node
		int left = curr * 2;
		int right = curr * 2 + 1;
		
		
		// decide who is smaller child which maybe need to swap
		Integer child;
		// only right 
		if (left >= this.slot && right < this.slot){
			child = right;
		}
		// only left
		else if (right >= this.slot && left < this.slot){
			child = left;
		}
		// both right, left exist, get the smaller one
		else if (right < this.slot && left < this.slot){
			child = null;
		}
		// both not exit, done
		else{
			return true;
		}
		
		// use nature ordering
		if (this.comparator == null){
			int result;
			// determine the child
			if (child == null){
				result  = ((Comparable) this.array[left]).compareTo(this.array[right]);
				// get the smaller one
				if (result < 0){
					child = left;
				}
				else{
					child = right;
				}
			}
			
			
			result = ((Comparable) this.array[curr]).compareTo(this.array[child]);
			// if current > child
			if (result > 0){
				// swap
				T tmp;
				tmp = this.array[curr];
				this.array[curr] = this.array[child];
				this.array[child] = tmp;
				
				if (this.percolateDown(child)){
					return true;
				}
				else{
					System.out.println("percolateDown failed");
					return false;
				}
			}
			else{
				return true;
			}
		}
		// use the comparator
		else{
			int result;
			// determine the child
			if (child == null){
				result = this.comparator.compare(this.array[left], this.array[right]);
				// get child as smaller one
				if (result < 0){
					child = left;
				}
				else{
					child = right;
				}
			}
			
			
			result = this.comparator.compare(this.array[curr], this.array[child]);
			// current > child
			if (result > 0){
				// swap
				T tmp;
				tmp = this.array[curr];
				this.array[curr] = this.array[child];
				this.array[child] = tmp;
				
				if (this.percolateDown(child)){
					return true;
				}
				else{
					System.out.println("percolateDown failed");
					return false;
				}
			}
			else{
				return true;
			}	
		}
	}
	/**
	 * Inserts the specified element into this priority queue.
	 * 
	 * @return <tt>true</tt>
	 * @throws ClassCastException
	 *             if the specified element cannot be compared with elements
	 *             currently in the priority queue according to the priority
	 *             queue's ordering.
	 * @throws NullPointerException
	 *             if the specified element is <tt>null</tt>.
	 */
	public boolean offer (T o)
	{
		// check input param
		if (o == null){
			return false;
		}
		
		// first check whether need to resize
		if (this.slot >= this.size){
			this.resize();
		}
		
		// insert new node then update the slot position
		this.array[this.slot] = o;
		this.slot++;
		
		// perform percolate
		if (this.percolate(this.slot-1)){
			return true;
		}
		else{
			return false;
		}
		
	}
	
	// Retrieves and removes the head of this queue, or null  if this queue is empty.
	public T poll ()
	{
		// check the status of the heap 
		if (this.isEmpty()){
			return null;
		}
		
		// if there is only one node
		if (this.slot == 2){
			this.slot--;
			return this.array[1];
		}
		
		// replace the head node by the last node
		T tmp = this.array[1];
		this.array[1] = this.array[slot-1];
	
		// remove the last node 
		this.slot--;
		
		// call percolateDown
		if (this.percolateDown(1)){
			return tmp;
		}
		else{
			throw new RuntimeException("Error at percolateDown");
		}
		
	}

	// Retrieves, but does not remove, the head of this queue, returning null if this queue is empty.
	public T peek()
	{
		if (this.isEmpty()){
			return null;
		}
		
		return this.array[1];
	}
	
	/**
	 * Returns an iterator over the elements in this queue. The iterator does
	 * not return the elements in any particular order. The iterator does not
	 * support the remove operation.
	 * 
	 * @return an iterator over the elements in this queue.
	 */
	@Override
    public Iterator<T> iterator ()
	{
		Iterator<T> iterator = new PriorityQueueIterator(this.array, this.slot);
		return iterator;
	}
	
	private static class PriorityQueueIterator<T> implements Iterator<T>{
		
		/* Implement your own constructor */
		private int heapSlot;
		private T[] array;
		private int curr;
		
		public PriorityQueueIterator(T[] array, int heapSlot){
			this.heapSlot = heapSlot;
			this.array = array;
			this.curr = 1;
		}
		
		public boolean hasNext(){
			if (this.curr >= this.heapSlot){
				return false;
			}
			else{
				return true;
			}
		}
		
		public T next(){
			if (this.hasNext()){
				T tmp = this.array[curr];
				this.curr++;
				return tmp;	
			}
			else{
				return null;
			}
		}
		
		public void remove(){
			throw new UnsupportedOperationException("This iterator does not support the remove operation.");
		}
	}
	
}
